package kyssion.leetcode.num201_250;


import java.util.*;

public class code208_前缀树 {


    /**
     * ["Trie","insert","search","search","search","startsWith","startsWith","startsWith"]
     * [[],["hello"],["hell"],["helloa"],["hello"],["hell"],["helloa"],["hello"]]
     * [null,null,false,false,true,true,false,true]
     *
     * @param args
     */

    public static void main(String[] args) {
        boolean ans;
        Trie trie = new Trie();
        trie.insert("jan");
//        ans = trie.search("hell");   // 返回 false
//        ans = trie.search("helloa");     // 返回 false
//        ans = trie.search("hello");     // 返回 true
//
//        ans = trie.startsWith("hell"); // 返回 true
        ans = trie.startsWith("jam"); // 返回 false
        ans = trie.startsWith("hello"); // 返回 true
    }

    static class Trie {

        Map<Character, Map> tree;
        Set<String> map;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            tree = new HashMap<>();
            map = new HashSet<>();
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            insert(word.toCharArray(), 0, tree);
            map.add(word);
        }

        private void insert(char[] arr, int index, Map<Character, Map> map) {
            if (index >= arr.length) {
                return;
            }
            if (map.containsKey(arr[index])) {
                insert(arr, index + 1, map.get(arr[index]));
            } else {
                map.put(arr[index], new HashMap());
                insert(arr, index + 1, map.get(arr[index]));
            }
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            return map.contains(word);
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            return startsWith(prefix.toCharArray(), 0, tree);
        }

        private boolean startsWith(char[] arr, int index, Map<Character, Map> mapMap) {
            if (index >= arr.length) {
                return true;
            }
            if (mapMap == null || !mapMap.containsKey(arr[index])) {
                return false;
            }
            return startsWith(arr, index + 1,mapMap.get(arr[index]));
        }
    }
}
